package 哈希表系列;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Intersection {

    //方法一：两个集合
//    public int[] intersection(int[] nums1, int[] nums2) {
//        if(nums1.length==0 || nums2.length == 0 || nums1 == null || nums2 == null){
//            return new int[0];
//        }
//
//        //利用set集合的特性，剔除重复元素
//        Set<Integer> set1 = new HashSet<>();    //保存nums1中的元素
//        Set<Integer> set2 = new HashSet<>();    //保存结果
//
//        for(int i : nums1){
//            set1.add(i);    //将元素添加到set1中，重复的将不添加
//        }
//
//        for(int i : nums2){
//            if(set1.contains(i)){
//                set2.add(i);    //如果set1中包含这个元素，则添加它
//            }
//        }
//
//        int[] result = new int[set2.size()];    //结果的数组
//        int index = 0;  //指针
//
//        for(int i : set2){
//            result[index++] = i;
//        }
//
//        return result;
//    }

    //方法二：排序 + 双指针
    public int[] intersection(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int length1 = nums1.length, length2 = nums2.length;
        int[] intersection = new int[length1 + length2];
        int index = 0, index1 = 0, index2 = 0;
        while (index1 < length1 && index2 < length2) {
            int num1 = nums1[index1], num2 = nums2[index2];
            if (num1 == num2) {
                // 保证加入元素的唯一性
                if (index == 0 || num1 != intersection[index - 1]) {
                    intersection[index++] = num1;
                }
                index1++;
                index2++;
            } else if (num1 < num2) {
                index1++;
            } else {
                index2++;
            }
        }
        return Arrays.copyOfRange(intersection, 0, index);
        //Arrays.copyOfRange(T[ ] original,int from,int to)
        //将一个原始的数组original，从下标from开始复制，复制到上标to，生成一个新的数组。
        //左闭右开
    }

}
